package demo3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class Solution {
    public List<List<Integer>> ret = new ArrayList<>();
    public LinkedList<Integer> list = new LinkedList<>();

    public void backTracking(int[] candidates, int target,int index,int sum){
        if(sum==target){
            ret.add(new ArrayList<>(list));
            return;
        }
        for(int i = index;i<candidates.length&&(sum + candidates[i]<=target);++i){
            if(i>index&&candidates[i]==candidates[i-1]){
                continue;
            }
            sum += candidates[i];
            list.add(candidates[i]);
            backTracking(candidates,target,i+1,sum);
            sum -= candidates[i];
            list.removeLast();
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTracking(candidates,target,0,0);
        return ret;
    }

    public static void main(String[] args) {
        //candidates = [10,1,2,7,6,1,5], target = 8,
        Solution solution = new Solution();
        int[] candidates = {10,1,2,7,6,1,5};
        int target = 8;
        String s = "ghj";
        solution.combinationSum2(candidates,target);
    }


}